package LeetCode.interview;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;
import util.LogUtils;

/*
 * 
原题

　　Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root). 
　　For example: 
　　Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

　　return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

题目大意

　　给定一棵二叉树自底向下进行层序遍历。 

解题思路
层序遍历二叉树是典型的广度优先搜索BFS的应用，但是这里稍微复杂一点的是，我们要把各个层的数分开，存到一个二维向量里面，
大体思路还是基本相同的，建立一个queue，
	然后先把根节点放进去，这时候找根节点的左右两个子节点，这时候去掉根节点，
	此时queue里的元素就是下一层的所有节点，用一个for循环遍历它们，然后存到一个一维向量里，
	遍历完之后再把这个一维向量存到二维向量里，以此类推，可以完成层序遍历。代码如下：

 * @Date 2017-09-13 22：39
 */
public class _107_Binary_Tree_Level_Order_Traversal_II {
	
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	    public TreeNode(int x, TreeNode l, TreeNode r) {val = x; left = l; right = r;}
	}

	/**
	 * 二叉树层序遍历：
	 * 	  将每一层的结果以头插法插到链表中(最后输出来就可以是倒序的)
	 * @param root
	 * @return
	 */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    	
    	
    	LinkedList<List<Integer>> rs =  new  LinkedList<List<Integer>>();
    	
    	if (root == null)	return rs;
    	
    	//层序遍历：使用队列实现
    	LinkedList<TreeNode> queue = new LinkedList<TreeNode>();

    	//将根节点加入队列
    	queue.add(root);
    	while (!queue.isEmpty()) {
    		LinkedList<Integer> layout = new LinkedList<Integer>(); 
    		//此时队列中的节点都是同一层的，全部取出
    		int size = queue.size();
    		for (int i = 0; i < size; i ++) {
    			TreeNode node = queue.removeFirst();
    			layout.add(node.val);
//    			LogUtils.print(node.val);
    			
    			//将下一层级的节点加入
    			if (node.left != null)
    				queue.add(node.left);
    			if (node.right != null)
    				queue.add(node.right);
    		}
//    		LogUtils.br();
    		//加入结果链表
    		rs.addFirst(layout);
    	}
    	//遍历：看下结果
//    	traverse(rs);
        return rs;
    }
    
    public void traverse (LinkedList<List<Integer>> rs) {
    	for (int i = 0; i < rs.size(); i ++) {
    		List<Integer> layout = rs.get(i);
    		for (int j = 0; j < layout.size(); j ++) {
    			LogUtils.print(layout.get(j));
    		}
    		LogUtils.br();
    	}
    }


    
    
	private TreeNode newTree1() {
		return new TreeNode(1, 
					new TreeNode(2, 
							new TreeNode(3, null, 
									new TreeNode(4)
							), null 
					), 
					new TreeNode(2, 
							null, 	new TreeNode(3, new TreeNode(4), null)
					)
				);
	}
	
	private TreeNode newTree2() {
		return new TreeNode(1, 
					new TreeNode(2, 
							new TreeNode(4, 
									new TreeNode(6), new TreeNode(7,
															null, new TreeNode(8))
							), new TreeNode(5)
					), 
					new TreeNode(3, 
							null, 	null)
				);
	}
	
	
	public static void main(String[] args) {
		_107_Binary_Tree_Level_Order_Traversal_II obj = new _107_Binary_Tree_Level_Order_Traversal_II();
		LogUtils.println("结果", 
				obj.levelOrderBottom(
//						obj.newTree2()
						null
				));
	}
}
